package leecode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author csp 2021-04-29
 */
public class Question20 {

    public boolean isValid(String s) {
        Map<Character,Character> map = new HashMap<Character,Character>(){{
            put('{','}'); put('[',']'); put('(',')'); put('?','?');
        }};
        if (s.length() > 0 && !map.containsKey(s.charAt(0))) {
            return false;
        }
        LinkedList<Character> stack = new LinkedList<Character>() {{ add('?'); }};
        for(Character c : s.toCharArray()){
            if (map.containsKey(c)) {
                stack.addLast(c);
            } else if (!map.get(stack.removeLast()).equals(c)) {
                return false;
            }
        }
        return stack.size() == 1;
    }
    public static void main(String[] args) {
        Question20 question20 = new Question20();
        System.out.println(question20.isValid("{[]}"));
    }
}
